#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e7;
bitset<N+1> b;
static int f[N+1];
inline ll l(int x,int y){
  return 1ll*x/__gcd(x,y)*y;
}
inline ll c(vector<int> a){
  ll c=0;
  for(int i=1;i<a.size();i++)
    c+=l(a[i-1],a[i]);
  return c;
}
int main(){
  freopen("never.in","r",stdin);
  freopen("never.out","w",stdout);
  ios::sync_with_stdio(false);
  cin.tie(0); cout.tie(0);
  for(int i=2;i<=N;i++)
    if(!b[i]){
      f[i]=i;
      for(int j=i<<1;j<=N;j+=i)
        if(!b[j])b[j]=true,f[j]=i;
    }
  int q; cin>>q;
  while(q--){
    int x,y,g; cin>>x>>y,g=__gcd(x,y);
    if(x==y)cout<<"0\n";
    else if(!(y%x))cout<<y<<'\n';
    else if(g>1)cout<<x+y<<'\n';
    else cout<<min({
      c({x,y}),c({x,2,y}),
      c({x,f[x],y}),c({x,f[y],y}),
      c({x,f[x],2,y}),c({x,2,f[y],y}),
      c({x,f[x],f[y],y}),c({x,f[x],2,f[y],y})
      })<<'\n';
  }
  return 0;
}